package 牛客算法篇;

import java.util.Stack;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-25
 * Time:19:39
 */

/**
 *
 牛客算法篇:BM11 链表相加(二)
 描述
 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 数据范围：0≤n,m≤10000000≤n,m≤1000000，链表任意值 0≤val≤90≤val≤9
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 示例1
 输入：
 [9,3,7],[6,3]
 返回值：
 {1,0,0,0}
 */
public class addInList {
    public static void main(String[] args) {
        ListNode a = new ListNode(9);
        ListNode b = new ListNode(3);
        ListNode c = new ListNode(7);
        ListNode d = new ListNode(6);
        ListNode e = new ListNode(3);


        a.next = b;
        b.next = c;

        d.next = e;
        addInList(a,d);
    }
    public static ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (head1 != null){
            stack1.push(head1.val);
            head1 = head1.next;
        }
        while (head2 != null){
            stack2.push(head2.val);
            head2 = head2.next;
        }
        ListNode output = new ListNode(0);
        int curry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || curry != 0){
            int sum = curry;
            if (!stack1.isEmpty()){
                sum += stack1.pop();
            }
            if (!stack2.isEmpty()){
                sum += stack2.pop();
            }
            ListNode tmp = new ListNode(sum % 10);
            tmp.next = output.next;
            output.next = tmp;
            curry = sum / 10;
        }
        return output.next;
    }
}
